package cn.bellychang.sword.finger.offer.question051;

/**
 * @author ChangLiang
 * @date 2021/1/30
 */
public class Solution2 {

    private int result;

    public int reversePairs(int[] nums) {
        if (nums.length == 0 || nums.length == 1) {
            return 0;
        }
        int[] target = new int[nums.length];
        splitAndMerge(0, nums.length - 1, nums, target);
        return result;
    }

    private void splitAndMerge(int beginIndex, int endIndex, int[] nums, int[] target) {
        if (beginIndex == endIndex) {
            target[beginIndex] = nums[beginIndex];
            return;
        }
        int middle = (endIndex - beginIndex) / 2 + beginIndex;
        splitAndMerge(beginIndex, middle, nums, target);
        splitAndMerge(middle + 1, endIndex, nums, target);
        int length = middle;
        for (int i = middle+1; i <= endIndex ; i++) {
            merge(beginIndex, length, target[i], target);
            length++;
        }
    }

    private void merge(int beginIndex, int middle, int value, int[] target) {
        // 这里两层for循环 造成超出时间限制
        for (int i = middle; i >= beginIndex ; i--) {
            if (target[i] <= value) {
                target[i + 1] = value;
                return;
            } else {
                target[i + 1] = target[i];
                result++;
            }
        }
        target[beginIndex] = value;
    }
}
